//
// Created by wenyaxi on 24-10-28.
//

#include <base.h>
#include <Printer.h>
using namespace std;

class Solution {
public:
    vector<int> element_data;

    vector<int>& sortArray(vector<int> &nums) {
        element_data = move(nums);
        qsort(0, element_data.size()-1);
        return element_data;
    }

    void qsort(int left,int right) {
        if(left >= right) return;
        int m=partition(left, right);
        qsort(left, m-1);
        qsort(m+1, right);
    }

    int partition(int left, int right) {
        default_random_engine generator;
        generator.seed(time(0));
        uniform_int_distribution<int> dist(left, right);

        int pivot = dist(generator);
        swap(element_data[left], element_data[pivot]);
        pivot=left;
        left++;
        int flag=1;
        while(left<=right) {
            if(flag==1) {
                if(element_data[pivot]>element_data[right]) {
                    swap(element_data[pivot], element_data[right]);
                    pivot=right;
                    flag=0;
                }
                right--;
            }else {
                if(element_data[pivot]<element_data[left]) {
                    swap(element_data[pivot], element_data[left]);
                    pivot=left;
                    flag=1;
                }
                left++;
            }
        }
        return pivot;
    }
};

int main() {
    //[5,2,3,1]
    //[5,1,1,2,0,0]
    auto s=make_unique<Solution>();
    vector<int> v={5,1,1,2,0,0};
    auto sort_array = s->sortArray(v);

    return 0;
}
